DFS offers efficient linear time performance, but its memory usage is directly tied to the graph's structure.

  • Time Complexity: The algorithm runs in $O(V+E)$ time because it visits every vertex and traverses every edge a constant number of times.
  • Space Complexity (Data): It requires $O(V)$ space for auxiliary data structures like the `visited` set and `parent` map.
  • Space Complexity (Stack): The critical factor is the recursion call stack. In the worst case, for a graph resembling a long path, the recursion can go $V$ levels deep, leading to $O(V)$ stack usage.
  • Key Tradeoff: Unlike BFS whose memory depends on the graph's width, the memory footprint of DFS is determined by its depth.
\[ \text{Time} = \mathcal{O}(V+E) \] \[ \text{Space} = \mathcal{O}(V) \text{ (data) } + \mathcal{O}(V) \text{ (stack worst-case)} \]